package SubjectTree.Five;

import Utility.TreeNode;

public class DeleteNode {

/**
 * 难度：中等
 * 
 * 450. 删除二叉搜索树中的节点
 * 	给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
 * 	并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * 	一般来说，删除节点可分为两个步骤：
 * 		首先找到需要删除的节点；
 * 		如果找到了，删除它。
 * 	
 * 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
 * 	
 * 示例:
 * 	root = [5,3,6,2,4,null,7]
 * 	key = 3
 * 	    5
 * 	   / \
 * 	  3   6
 * 	 / \   \
 * 	2   4   7
 * 	给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * 	一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * 	    5
 * 	   / \
 * 	  4   6
 * 	 /     \
 * 	2       7
 * 	另一个正确答案是 [5,2,6,null,4,null,7]。
 * 	    5
 * 	   / \
 * 	  2   6
 * 	   \   \
 * 	    4   7
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		DeleteNode dn = new DeleteNode();
		System.out.println(dn.deleteNode1(TreeNode.MkTree("[5,3,6,2,4,null,7]"), 5));
	}
	//自己写(递归)
	public TreeNode deleteNode(TreeNode root, int key) {
		/*
         * 有以下五种情况：
         * 第一种情况：没找到删除的节点，遍历到空节点直接返回了
         * 找到删除的节点
         * 	第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
         * 	第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
         * 	第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
         * 	第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的
         * 	最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
         * */
        if(root==null)return root;//第一种
        
        if(root.val == key) {
        	if(root.left==null && root.right==null)return null;				//第二种
        	else if(root.left==null && root.right!=null)return root.right;	//第三种
        	else if(root.left!=null && root.right==null)return root.left;	//第四种
        	else if(root.left!=null && root.right!=null) {					//第五种
        		TreeNode node = root.right;
        		while(node.left!=null) {
        			node = node.left;
        		}
        		//把左子树放到右子树的最左下方
        		node.left = root.left;
        		//返回右子树
        		return root.right;
        	}
        }
        
        if (root.val > key)root.left = deleteNode(root.left, key);
        if (root.val < key)root.right = deleteNode(root.right, key);
		return root;
    }
	//自己写(迭代)
	public TreeNode deleteNode_1(TreeNode root, int key) {
		if(root==null)return root;//第一种
		
		TreeNode cur = root;
		// 记录cur的父节点，用来删除cur
		TreeNode pre = null;
		
		while(cur!=null) {
			if(cur.val == key) break;
			pre = cur;
			if(cur.val > key) cur = cur.left;
			else cur = cur.right;
		}
		// 删除根节点或者root = null
		if(pre == null) {
			return deleteOneNode(cur);
		}
		if(pre.left!=null && pre.left.val == key) {
			pre.left = deleteOneNode(cur);
		}
		if(pre.right!=null && pre.right.val == key) {
			pre.right = deleteOneNode(cur);
		}
		return root;
	}
	private TreeNode deleteOneNode(TreeNode target) {
        if (target == null) return target;				//第一种
        if (target.right == null) return target.left;	//第三种
        TreeNode cur = target.right;					//第四种		
        while (cur.left!=null) {						
            cur = cur.left;
        }
        //把左子树放到右子树的最左下方
        cur.left = target.left;
        //返回右子树
        return target.right;
    }
	
	//方法：递归
	/*
	  One step right and then always left
	 */
	public int successor(TreeNode root) {
	    root = root.right;
	    while (root.left != null) root = root.left;
	    return root.val;
	}

	/*
	  One step left and then always right
	*/
	public int predecessor(TreeNode root) {
	    root = root.left;
	    while (root.right != null) root = root.right;
	    return root.val;
	}
	public TreeNode deleteNode1(TreeNode root, int key) {
	    if (root == null) return null;

	    // delete from the right subtree
	    if (key > root.val) root.right = deleteNode1(root.right, key);
	    // delete from the left subtree
	    else if (key < root.val) root.left = deleteNode1(root.left, key);
	    // delete the current node
	    else {
	      // the node is a leaf
	      if (root.left == null && root.right == null) root = null;
	      // the node is not a leaf and has a right child
	      else if (root.right != null) {
	        root.val = successor(root);
	        root.right = deleteNode1(root.right, root.val);
	      }
	      // the node is not a leaf, has no right child, and has a left child    
	      else {
	        root.val = predecessor(root);
	        root.left = deleteNode1(root.left, root.val);
	      }
	    }
	    return root;
	}
}
